package problem236;

import java.util.Stack;

//236.二叉树的最近公共祖先
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root, stack1, p);
        getPath(root, stack2, q);
        while(stack1.size() > stack2.size()) {
            stack1.pop();
        }
        while(stack2.size() > stack1.size()) {
            stack2.pop();
        }
        while(stack1 != null) {
            if(stack1.peek() == stack2.peek()) {
                return stack1.pop();
            }
            stack1.pop();
            stack2.pop();
        }
        return null;
    }


    public boolean getPath(TreeNode root, Stack<TreeNode> stack, TreeNode tar) {
        if(root == null) return false;
        stack.push(root);
        if(root == tar) return true;
        boolean res1 = getPath(root.left, stack, tar);
        if(res1) return true;
        boolean res2 = getPath(root.right, stack, tar);
        if(res2) return true;
        stack.pop();
        return false;
    }
}